#pragma once
#include<iostream>
using namespace std;

template<class T>
struct TreeNode {
	T element;
	TreeNode<T>*parent, *left, *right;
	TreeNode() {
		parent = NULL;
		left = NULL;
		right = NULL;
	}
	TreeNode(T &key) {
		element = key;
		parent = NULL;
		left = NULL;
		right = NULL;
	}
};

template<class T>
class BinaryTree
{
private:
	TreeNode<T> *root;

public:
	BinaryTree() :root(NULL) {}
	~BinaryTree();

	template<class T>
	void Inorder(TreeNode<T> *node) {  //node is root;
		if (node == NULL) {
			return;
		}
		else {
			Inorder(node->left);
			cout << node->element << " ";
			Inorder(node->right);
		}
	}

	template<class T>
	void Insert(T key) {
		TreeNode<T> *x = root;
		TreeNode<T> *p = NULL;
		TreeNode<T> *c = new TreeNode<T>(key);
		while (x != NULL) {
			p = x;
			if (c->element < x->element)
				x = x->left;
			else
				x = x->right;
		}
		c->parent = p;
		if (p == NULL) {
			root = c;
		}
		else if (c->element > p->element)
			p->right = c;
		else
			p->left = c;
	}

	TreeNode<T> *GetRoot() {
		return root;
	}

	template<class T>
	TreeNode<T> *BinaryTreeSearch(TreeNode<T> *Tree, T key) {
		cout << endl << "Search " << key << " start . " << endl;
		if (Tree == NULL || key == Tree->element) {
			if (Tree == NULL) {
				cout << key << " not found ! " << endl;
			}
			else {
				cout << key << " found ! " << endl;
			}
			return Tree;
		}
		if (key > Tree->element)
			return BinaryTreeSearch(Tree->right, key);
		else
			return BinaryTreeSearch(Tree->left, key);
	}
};

